package com.leetcode.study.suixianglu;


import java.util.Arrays;

/**
 * 删除数组中的特定元素
 */
public class DeleteElementInArray {


    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 3, 4, 3, 5};
        System.out.println("移除前>>>>>>>>> " + Arrays.toString(arr));
        int delTarget = 5;
        delete2(arr, delTarget);
        System.out.println("移除后>>>>>>>>> " + Arrays.toString(arr));
    }

    /**
     * 删除元素，暴力删除, 时间复杂度O(n^2)
     *
     * @param arr
     * @param delTarget
     * @return
     */
    private static void delete1(int[] arr, int delTarget) {
        int newSize = arr.length;
        /**
         * 使用双重for循环来做：
         * 1、第一层for循环用来遍历找到目标值
         * 2、第二层for循环用来把目标元素后面的
         */
        for (int i = 0; i < arr.length; i++) {
            int v = arr[i];
            if (delTarget != v) {
                continue;
            }
            newSize--;
            for (int j = i + 1; j < arr.length; j++) {
                arr[j - 1] = arr[j];
            }
        }

        for (int i = newSize; i < arr.length; i++) {
            arr[i] = -1;
        }
    }


    /**
     * 删除元素，双指针 时间复杂度O(n)
     * 定义快慢指针：
     * 快指针：寻找老数组中满足条件的元素的指针，比如移除3，快指针就是寻找不等于3
     * 慢指针：新的数组的下标指针，用于操作写新的数组
     * @param arr
     * @param delTarget
     * @return
     */
    private static void delete2(int[] arr, int delTarget) {
        int newSize = arr.length;

        // 快指针要遍历整个老数组中，满足条件的元素
        for (int fast = 0, slow = 0; fast < arr.length; fast++) {

            int v = arr[fast];

            // 删除的元素不需要保存，不是删除的元素就要存入慢指针所在的数组
            if (v != delTarget) {
                // 把快指针指向的元素赋值给慢指针指向的位置
                arr[slow] = v;
                // 慢指针往后移动一位
                slow++;
                continue;
            }

            newSize--;
        }

        for (int i = newSize; i < arr.length; i++) {
            arr[i] = -1;
        }
    }

}
